// https://leetcode.cn/problems/check-permutation-lcci/

// 算法思路总结：
// 1. 使用数组哈希统计字符出现频率
// 2. 遍历字符串，一个加计数一个减计数
// 3. 最后检查所有字符计数是否归零
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <string>

class Solution 
{
public:
    bool CheckPermutation(string s1, string s2) 
    {
        int n1 = s1.size(), n2 = s2.size();
        if (n1 != n2) return false;

        int hash[26] = {0};
        for (int i = 0 ; i < n1 ; i++)
        {
            hash[s1[i] - 'a']++;
            hash[s2[i] - 'a']--;
        }

        for (int& num : hash)
            if (num) return false;
        return true;
    }
};

int main()
{
    string s11 = "abc", s12 = "bca";
    string s21 = "abc", s22 = "bad";

    Solution sol;
    cout << sol.CheckPermutation(s11, s12) << endl;
    cout << sol.CheckPermutation(s21, s22) << endl;

    return 0;
}